Mr笔记

Appearance

S15-06 算法-图结构、深度、广度优先算法 ​

[TOC]

图结构 Graph ​

概述 ​

什么是图 ​

图(Graph) 是一种由顶点和边组成的数据结构，用于表示对象之间的关系。

  • 顶点(Vertex)：V，图中的元素或对象。
  • 边(Edge)：E，连接两个顶点的线，表示顶点之间的关系或连接。边可以是有向的或无向的。
    • A --- B，通常表示无向。
    • A --> B，通常表示有向
  • 树是图结构的一种。

在计算机程序设计中，图结构 也是一种非常常见的数据结构。

  • 但是，图论其实是一个非常大的话题
  • 我们通过本章的学习来认识一下关于图的一些内容：图的抽象数据类型，一些算法实现。

我们知道树可以用来模拟很多现实的数据结构

  • 比如： 家谱/公司组织架构等等
  • 那么图长什么样子?
  • 或者什么样的数据使用图来模拟更合适呢?

图的现实案例 ​

人与人之间的关系网：

甚至科学家们在观察人与人之间的关系网时，还发现了六度空间理论。

六度空间理论(Six Degrees of Separation)：理论上认为世界上任何两个互相不认识的两人。只需要很少的中间人就可以建立起联系。并非一定要经过6步，只是需要很少的步骤。

image-20240911172012841


北京地铁图：

image-20250122153852795


村庄间的关系网：

image-20250122153828579

我们会发现，上面的节点(其实图中叫顶点Vertex)之间的关系，是不能使用树来表示的。使用任何的树结构都不可以模拟。这个时候，我们就可以使用图来模拟它们。

七桥问题 ​

七桥问题：

18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来（如图）。有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。

image-20240911172059727

问题进展：

1735年，有几名大学生写信给当时正在俄罗斯的彼得斯堡科学院任职的天才数学家欧拉，请他帮忙解决这一问题。欧拉在亲自观察了哥尼斯堡七桥后，认真思考走法，但始终没能成功，于是他怀疑七桥问题是不是原本就无解呢？

1736年，在经过一年的研究之后，29岁的欧拉提交了《哥尼斯堡七桥》的论文，圆满解决了这一问题，同时开创了数学新一分支——图论。1736年被称为图论诞生的元年。

欧拉解答：

  • 图的抽象：将柯尼斯堡的七座桥和四个陆地区域(两个岛屿和两岸的土地)抽象成一个图。

    image-20250122165938446

  • 度数：在图论中，顶点的“度”指的是与该节点相连的边的数量。

    • 奇点：边的数量为奇数。
    • 偶点：边的数量为偶数。

  • 结论：如果一个图存在一个有效的路径，使得每条边都被走一次并且最终回到起点，那么这个图必须满足以下条件：

    • 图形必须是连通的。

    • 图中的“奇点”个数是0或2。

      image-20250122171055432

  • 其他结论：

    • 奇点个数必为偶数：2k。
    • 需要k笔画完。
    • 可以增加k-1条线，形成欧拉路径。
    • 可以增加k条线，形成欧拉回路。

  • 弗勒里算法： 用于寻找欧拉路径或欧拉回路的算法。

    • 画一条线，删一条线。
    • 不要让图形断开。

个人思考：

  • 欧拉在思考这个问题的时候，并不是针对某一个特性的问题去考虑，而是将岛和桥抽象成了点和线。
  • 抽象是数学的本质，而编程我们也一再强调抽象的重要性。
  • 汇编语言是对机器语言的抽象，高级语言是对汇编语言的抽象。
  • 操作系统是对硬件的抽象，应用程序在操作系统的基础上构建。

图的术语 ​

我们在学习树的时候，树有很多的相关术语。了解这些术语有助于我们更好的理解树结构。

我们也来学习一下图相关的术语。但是图的术语其实非常多，如果你找一本专门讲图的各个方面的书籍，会发现只是术语 就可以占据满满的一个章节。

这里，我们先介绍几个比较常见的术语，某些术语后面用到的时候，再了解。没有用到的，在自行深入学习的过程中，可以通过查资料去了解。

我们先来看一个抽象出来的图，用数字更容易我们从整体来观察整个图结构。

image-20240911172156638

顶点：表示图中的一个节点。如地铁站中某个站/多个村庄中的某个村庄/互联网中的某台主机/人际关系中的人。

边：表示顶点和顶点之间的连线。如地铁站中两个站点之间的直接连线。

  • 注意：这里的边不要叫做路径，路径有其他的概念。

相邻顶点：由一条边连接在一起的顶点称为相邻顶点。

度：表示相邻顶点的数量。

  • 比如0顶点和其他两个顶点相连，0顶点的度是2
  • 比如1顶点和其他四个顶点相连，1顶点的度是4

路径：表示顶点v1，v2...，vn的一个连续序列，如上图中0 1 5 9就是一条路径。

  • 简单路径：简单路径要求不包含重复的顶点。如 0 1 5 9是一条简单路径。
  • 回路：第一个顶点和最后一个顶点相同的路径。如 0 1 5 6 3 0。

无向图：表示所有的边都没有方向。

  • 比如 0 - 1之间有变，那么说明这条边可以保证 0 -> 1，也可以保证 1 -> 0。

有向图：表示图中的边是有方向的。

  • 比如 0 -> 1，不能保证一定可以 1 -> 0，要根据方向来定。

无权图：表示边没有权重。

带权图：表示边有一定的权重。权重可以是任意你希望表示的数据：距离、花费时间或票价等。

image-20250122173452091

图的程序表示 ​

我们知道一个图包含很多顶点，另外包含顶点和顶点之间的连线(边)。这两个都是非常重要的图信息，因此都需要在程序中体现出来。

顶点的程序表示：

顶点的程序表示相对简单，我们先讨论顶点的表示。

  • 上面的顶点，我们抽象成了1 2 3 4，也可以抽象成A B C D。
  • 在后面的案例中，我们使用A B C D。
  • 那么这些A B C D我们可以使用一个数组来存储起来(存储所有的顶点)
  • 当然，A，B，C，D也可以表示其他含义的数据(比如村庄的名字)

边的程序表示：

  • 因为边是两个顶点之间的关系，所以表示起来会稍微麻烦一些。
  • 下面，我们具体讨论一下边常见的表示方式。
    • 邻接矩阵
    • 邻接表
邻接矩阵 ​

邻接矩阵(Adjacency Matrix) 是图论中用来表示图的一种矩阵形式。假设有一个图G = (V, E)，若图G有n个顶点，则邻接矩阵是一个n × n的矩阵，其中的元素表示图中顶点之间是否有边相连。

  • 对于一个无向图，邻接矩阵是对称的。
  • 对于一个有向图，邻接矩阵一般不对称。
  • image-20250122174955299

程序表示：

  • 让每个节点和一个整数项关联，该整数作为数组的下标值。
  • 我们用一个二维数组来表示顶点之间的连接。
  • 二维数组[0][2] -> A -> C

画图演示：

image-20240911172312080

  • 在二维数组中，0表示没有连线，1表示有连线。
  • 通过二维数组，我们可以很快的找到一个顶点和哪些顶点有连线。(比如A顶点，只需要遍历第一行即可)
  • 另外，A - A，B - B(也就是顶点到自己的连线)，通常使用0表示。

邻接矩阵的问题：

  • 如果图是一个稀疏图，那么矩阵中将存在大量的0，这意味着我们浪费了计算机存储空间来表示根本不存在的边。
邻接表 ​

邻接表(Adjacency List) 是图的一种常见表示方法，它通过*链表(数组/哈希表)*的形式来存储图的边。每个顶点都有一个链表，其中存储了与该顶点相邻的所有顶点。

画图演示：

image-20240911172321495

  • 比如我们要表示和A顶点有关联的顶点(边)，A和B/C/D有边，
  • 那么我们可以通过A找到对应的数组/链表/字典，再取出其中的内容就可以了。

邻接表的问题：

  • 邻接表计算"出度"是比较简单的。

    • 出度：指向别人的数量。
    • 入度：指向自己的数量。

  • 邻接表如果需要计算有向图的"入度"，那么是一件非常麻烦的事情。

    • 它必须构造一个“逆邻接表”，才能有效的计算“入度”。
    • 但是开发中“入度”相对用的比较少。

图的实现 ​

Graph 类 ​

我们先来创建Graph类

image-20250122180732287

Graph：class，图的构造方法。

  • vertexes：[]，用于存储所有的顶点。
  • adjList：Map，用于存储所有的边，我们这里采用邻接表的形式。

之后，我们来定义一些方法以及实现一些算法就是一个完整的图类了

添加方法 ​

现在我们来增加一些添加方法。

  • addVertex()：(vertex)，向图中添加一些顶点vertex。
  • addEdge：(v1, v2)，添加顶点v1和顶点v2之间的边。

1、封装添加顶点方法addVertex()

image-20250122214349731

测试

image-20250122214621957

2、封装添加边方法addEdge()

image-20250122214359040

测试

js
// 添加边
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

image-20250122215115924

traverse() 遍历 ​

为了能够正确的显示图的结果，我们来实现一下Graph的printEdges方法

image-20250122215623835

深度、广度优先算法 ​

图的遍历 ​

图的遍历思想：

  • 图的遍历思想和树的遍历思想是一样的。
  • 图的遍历意味着需要将图中每个顶点访问一遍，并且不能有重复的访问。

图的变量算法： 两种遍历算法，都需要明确指定第一个被访问的顶点。

  • 广度优先搜索(BFS，Breadth-First Search)
  • 深度优先搜索(DFS，Depth-First Search)

示例：迷宫关灯：

我们以一个迷宫中关灯为例。现在需要你进入迷宫，将迷宫中的灯一个个关掉，你会怎么关呢?

image-20240911172448974

遍历思路 ​

两种算法的思想：

  • BFS： 基于队列，入队列的顶点先被探索。
  • DFS： 基于栈或使用递归，通过将顶点存入栈中，顶点是沿着路径被探索的，存在新的相邻顶点就去访问。

为了记录顶点是否被访问过，我们使用三种颜色来反应它们的状态

  • 白色： 表示该顶点还没有被访问。
  • 灰色： 表示该顶点被访问过，但并未被探索过。
  • 黑色： 表示该顶点被访问过且被完全探索过。

或者我们也可以使用Set来存储被访问过的节点

图的实现-续 ​

bfs() 广度优先搜索 ​

BFS： 广度优先搜索会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。换句话说，就是先宽后深的访问顶点。

图解BFS：

image-20240911172500651

实现思路：

思路一：

  • 创建一个队列Q。

  • 将v标注为被发现的(灰色)，并将v将入队列Q

  • 如果Q非空，执行下面的步骤：

    • 将v从Q中取出队列。

    • 将v标注为被发现的灰色。

    • 将v所有的未被访问过的邻接点(白色)，加入到队列中。

    • 将v标志为黑色。

思路二： 使用set()替代标记颜色的方法。


代码实现：

image-20250123105413729

dfs() 深度优先搜索 ​

DFS： 深度优先搜索搜索将会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后被访问了。接着原路回退并探索下一条路径。

image-20250123112904494

实现思路： 广度优先搜索算法我们使用的是队列，这里可以使用栈完成，也可以使用递归。为了方便代码书写，我们还是使用递归(递归本质上就是函数栈的调用)


代码实现：

image-20250123112631510

图的建模 ​

交通流量建模：

  • 顶点可以表示街道的十字路口，边可以表示街道。
  • 加权的边可以表示限速或者车道的数量或者街道的距离。
  • 建模人员可以用这个系统来判定最佳路线以及最可能堵车的街道。

飞机航线建模：

  • 航空公司可以用图来为其飞行系统建模。
  • 将每个机场看成顶点，将经过两个顶点的每条航线看作一条边。
  • 加权的边可以表示从一个机场到另一个机场的航班成本，或两个机场间的距离。
  • 建模人员可以利用这个系统有效的判断从一个城市到另一个城市的最小航行成本。